package demo1;
import java.util.Scanner;

public class DynamicPlanningPractise {
    /**
     * 让字符串成为回文串的最小插入次数
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）
     */
    public int minInsertions(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化 - 无需初始化
        //3 填表
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                if (chars[i] == chars[j])
                    dp[i][j] = dp[i + 1][j - 1];
                else
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
        //4 返回值
        return dp[0][n - 1];
    }

    /**
     * 不相交的线-实际上就是求两个数组中最长公共子序列
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）
     */
        public int maxUncrossedLines(int[] nums1, int[] nums2) {
            int i = nums1.length;
            int j = nums2.length;
            //1 创建dp表 - 使用虚拟位置法进行初始化
            int[][] dp = new int[i + 1][j + 1];
            //2 初始化 - 将第一行第一列初始化为0，故无需处理
            //3 填表
            for (int x = 1; x <= i; x++)
                for (int y = 1; y <= j; y++)
                    if (nums1[x - 1] == nums2[y - 1])
                        dp[x][y] = dp[x - 1][y - 1] + 1;
                    else
                        dp[x][y] = Math.max(dp[x][y - 1], dp[x - 1][y]);
            //4 返回值
            return dp[i][j];
        }
        /**
         * 正则表达式匹配
         * 时间复杂度O（n*n）
         * 空间复杂度O（n*n）*/
        public boolean isMatch(String s1, String p1) {
            //i表示s的范围，j表示p的范围
            //m表示s的长度，n表示p的长度
            int m = s1.length();
            int n = p1.length();
            //处理下标映射关系
            s1 = " "+s1;
            p1 = " "+p1;
            char[] s = s1.toCharArray();
            char[] p = p1.toCharArray();
            //1 创建dp表 - 使用虚拟位置法，多创建一行一列
            boolean[][] dp = new boolean[m+1][n+1];
            //2 初始化
            dp[0][0] = true;
            for(int k = 2; k <= n; k+=2)
                if(p[k]=='*')
                    dp[0][k] = true;
                else break;
            //3 填表
            for(int i = 1; i <= m; i++)
                for(int j = 1; j <= n; j++)
                    if(p[j]=='*')
                        dp[i][j] = dp[i][j-2] || (p[j-1]=='.' || s[i]==p[j-1]) && dp[i-1][j];
                    else if(p[j]=='.' || s[i]==p[j])
                        dp[i][j] = dp[i-1][j-1];
            //4 返回值
            return dp[m][n];
        }

        /**
         * 交错字符串
         * 时间复杂度O（n*n）
         * 空间复杂度O（n*n）*/
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        //处理边界情况
        if(m+n != s3.length()) return false;
        //对字符串进行预处理
        s1 = " "+s1;
        s2 = " "+s2;
        s3 = " "+s3;
        //1 创建dp表 - 使用虚拟位置法进行初始化，多创建一行一列
        boolean[][] dp = new boolean[m+1][n+1];
        //2 初始化
        dp[0][0] = true;
        for(int k = 1; k <= n; k++)
            if(s2.charAt(k)==s3.charAt(k))
                dp[0][k]=true;
            else break;
        for(int k = 1; k <= m; k++)
            if(s1.charAt(k)==s3.charAt(k))
                dp[k][0]=true;
            else break;
        //3 填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            /**前面我在此处使用if else出错，是因为，若是if正确后 若是里面的赋值表达式不正确
             则会导致else不再进行判断 这实际上是错误的逻辑 要及时改正 */
                dp[i][j] = s3.charAt(i+j)==s1.charAt(i) && dp[i-1][j] ||
                        s3.charAt(i+j)==s2.charAt(j) && dp[i][j-1];
        //4 返回值
        return dp[m][n];
    }

    /**
     * 两个字符串的最小ASCII删除和
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int minimumDeleteSum(String s1, String s2) {
        //求最长公共子序列中ASCII码总和最大的一组
        /**
         状态表示：
         dp[i][j] = 表示s1[0,i]范围 与 s2[0,j]范围 两个范围所有子序列中，最长公共子序列的ASCII码值总和
         状态转移方程：- 根据最后一个元素的状态进行划分
         情况一：s1[i]==s2[j] dp[i][j] += dp[i-1][j-1]+s1[i]
         情况二：s1[i]!=s2[j] dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
         初始化：
         引入空串 + 虚拟位置法 + 字符串辅助位置法
         不论是s1为空还是s2为空，其最大公共子序列均为空，故全部初始化为0
         填表顺序：
         从上到下，从左到右
         */
        //m 表示 s1 的长度； n 表示 s2 的长度
        //i 表示 s1 的范围； j 表示 s2 的范围
        int m = s1.length(); int n = s2.length();
        //处理下标映射关系
        s1 = " "+s1; s2 = " "+s2;
        char[] ss1 = s1.toCharArray();
        char[] ss2 = s2.toCharArray();
        int sum = 0;
        for(int k = 1; k <= m; k++)
            sum += ss1[k];
        for(int k = 1; k <= n; k++)
            sum += ss2[k];
        //1 创建dp表 - 虚拟位置法 多创建一行一列
        int[][] dp = new int[m+1][n+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(ss1[i]==ss2[j])
                    dp[i][j] += dp[i-1][j-1]+ss1[i];
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
        //4 返回值
        return sum-dp[m][n]-dp[m][n];
    }

    /**
     * 最长重复子数组
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）
     * 本题是两个数组的dp问题-子数组，较为简单*/
    public int findLength(int[] nums1, int[] nums2) {
        /**
         状态表示：
         dp[i][j]表示nums1数组以i下标元素为结尾的所有子数组 nums2数组以j下标元素为结尾的所有子数组 这两个范围子数组中 最长的公共子数组
         状态转移方程：
         情况一：nums1[i]==nums2[j],dp[i][j] = dp[i-1][j-1]+1;
         情况二：nums1[i]!=nums2[j],dp[i][j] = 0 -- > 本题是子数组问题，若是最后一个元素的值都不相同，那么与前面也就连接不上;
         初始化：
         引入空数组的概念，并使用虚拟位置法初始化
         第一行代表nums1的子数组为空，dp[0][x]=0
         第一列代表nums2的子数组为空，dp[x][0]=0
         由于是数组，故无法处理下标映射关系
         填表顺序：
         从上到下
         */
        //m 表示 nums1的长度， n 表示 nums2的长度
        int m = nums1.length; int n = nums2.length;
        //1 创建dp表 - 使用虚拟位置法，多创建一行一列
        int[][] dp = new int[m+1][n+1];
        //2 初始化 - 无需初始化
        //3 填表
        int ret = 0;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++) {
                if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
                ret = Math.max(ret,dp[i][j]);
            }
        //4 返回值
        return ret;
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        //接收输入
        int n = in.nextInt();
        int V = in.nextInt();
        int[][] item = new int[n+1][3];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= 2; j++)
                item[i][j] = in.nextInt();
        /**
         状态表示：
         dp[i][j]表示在挑选第i件物品时，其体积（小于等于j）不超过j的情况下，所能挑选的最大价值
         状态转移方程：
         我们在挑选第i件物品时，可能有两种情况，如下：
         1，第i件物品不选，故dp[i][j]=dp[i-1][j]
         2，第i件物品必选，此时需要满足当前的体积能够装下第i件物品 即是j-item[i][1]>=0
         若是成立，则dp[i][j] = item[i][2]+dp[i-1][j-item[i][1]],若是不成立，则为0
         初始化：
         由于我们在接收输入时采取的是从1下标开始，故此处我们可以选择虚拟位置法进行初始化
         虚拟位置赋值：
         第一行代表第0号物品但是我们并不存在第0号物品，故其最大价值为0
         第一列代表体积为0，体积为0无意义，故为0
         下标映射关系：
         item与dp下标一一对应
         填表顺序：
         由状态转移方程可得，填表顺序为从上到下
         */
        //1 创建dp表
        int[][] dp = new int[n+1][V+1];
        //2 初始化 - 无需初始化
        //3 填表
        int[] ret = new int[2];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= V; j++) {
                int tmp = j-item[i][1];
                dp[i][j] = tmp>=0 ? Math.max(item[i][2]+dp[i-1][tmp],dp[i-1][j]) : dp[i-1][j];
                ret[0] = Math.max(ret[0],dp[i][j]);
                if(j==V) ret[1] = Math.max(ret[1],dp[i][j]);
            }
        //4 返回值
        System.out.println(ret[0]);
        System.out.println(ret[1]);
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        //接收输入
        int n = in.nextInt();
        int V = in.nextInt();
        int[][] item = new int[n+1][3];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= 2; j++)
                item[i][j] = in.nextInt();
        //(1)
        /**
         状态表示：
         dp[i][j]表示在挑选第i件物品时，其体积（小于等于j）不超过j的情况下，所能挑选的最大价值
         状态转移方程：
         我们在挑选第i件物品时，可能有两种情况，如下：
         1，第i件物品不选，故dp[i][j]=dp[i-1][j]
         2，第i件物品必选，此时需要满足当前的体积能够装下第i件物品 即是j-item[i][1]>=0
         若是成立，则dp[i][j] = item[i][2]+dp[i-1][j-item[i][1]],若是不成立，则为0
         初始化：
         由于我们在接收输入时采取的是从1下标开始，故此处我们可以选择虚拟位置法进行初始化
         虚拟位置赋值：
         第一行代表我们选择0号物品，此时在体积不炒过j时的最大价值，由于0号物品无价值，故为0
         第一列代表体积为0，体积为0无意义，故为0
         下标映射关系：
         item与dp下标一一对应
         填表顺序：
         由状态转移方程可得，填表顺序为从上到下
         */
        //1 创建dp表
        int[][] dp = new int[n+1][V+1];
        int[][] dpp = new int[n+1][V+1];
        //2 初始化 - 无需初始化
        //3 填表
        int[] ret = new int[2];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= V; j++) {
                int tmp = j-item[i][1];
                //填表第一个
                dp[i][j] = tmp>=0 ? Math.max(item[i][2]+dp[i-1][tmp],dp[i-1][j]) : dp[i-1][j];
                ret[0] = Math.max(ret[0],dp[i][j]);
                //填表第二个
                if(tmp>=0)
                    dpp[i][j] =
                if(j==V) ret[1] = Math.max(ret[1],dpp[i][j]);
            }
        //4 返回值
        System.out.println(ret[0]);
        System.out.println(ret[1]);
        //(2)
        /**
         状态表示：
         dp[i][j]表示在挑选第i件物品时，其体积等于j的情况下，所能挑选的最大价值
         状态转移方程：
         此时存在两种情况：
         第i件物品不选，则dp[i][j] = dp[i-1][j]
         第i件物品必选，则需要满足 j-item[i][1]>=0 && 此处需保证剩余空间刚好被装满
         即是需要满足当前背包容量能够装下第i件物品，并且在装下第i件物品后，其剩余的空间刚好被装满
         初始化：
         由于我们在接收输入时采取的是从1下标开始，故此处我们可以选择虚拟位置法进行初始化
         虚拟位置赋值：
         第一行代表第0号物品但是我们并不存在第0号物品，故其最大价值为0
         第一列代表体积为0，体积为0无意义，故为0
         下标映射关系：
         item与dp下标一一对应
         填表顺序：
         由状态转移方程可得，填表顺序为从上到下
         */
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //接收数据
        int n = in.nextInt();//物品个数
        int V = in.nextInt();//背包体积
        //接收每个物品的体积和价值 - 从 1-1开始装
        int[][] item = new int[n+1][3];
        for(int k = 1; k <= n; k++) {
            item[k][1] = in.nextInt();
            item[k][2] = in.nextInt();
        }

        /**
         (1)求该背包最多能装多大价值的物品 - 不一定要装满
         状态表示：
         dp[i][j]表示在挑选第i号物品时，物品体积不超过j时（小于等于），所能装的最大价值
         状态转移方程：
         分两种情况：
         第i件物品不装：dp[i][j] = dp[i-1][j]
         第i件物品装：j>=item[i][1] ==> dp[i][j] = item[i][2]+dp[i-1][tmp](为了保证最大，需要求max); tmp = j-item[1];
         初始化：
         我们采取的是虚拟位置法
         虚拟位置赋值：
         第一行表示选择或者不选0号物品 并且 体积不超过0/1/2/3/4...时，我们此时的最大价值，由于0号物品不存在，故价值0体积0，选或不选都是0
         第一列表示选择0/1/2/3/4..号物品，并且体积不超过0时，此时的最大价值，由于不存在0体积的物品，故均无法选择，最高价值为0
         填表顺序：
         从上到下，从左到右

         （2）求该背包恰好装满时，最多能装多大价值的物品
         状态表示：
         dpp[i][j]表示在挑选第i号物品时，物品体积等于j，所能装的最大价值
         状态转移方程：
         分两种情况：
         第i件物品不装：dpp[i][j] = dpp[i-1][j] 此时有可能dpp[i-1][j]不能符合状态表示，我们将此类情况用-1表示
         第i件物品装：j>=item[i][1] && dpp[i-1][tmp]!=-1 ==> dpp[i][j] = Math.max(dpp[i][j],item[i][2]+dpp[i-1][tmp]);
         初始化： 我们采取的是虚拟位置法
         虚拟位置赋值：
         dpp[0][0]表示选择0号物品，并且此时体积正好等于0，此时所能装的最大价值，0号物品不存在，故选或不选体积均为0，且最大价值也为0
         第一行从1下标开始即是表示 第一行表示选择或者不选0号物品 并且 体积等于0/1/2/3/4...时，我们此时的最大价值，由于0号物品不存在，故价值0体积0，无法构成体积条件，故使用-1表示
         第一列表示选择0/1/2/3/4..号物品，并且体积等于0时，此时的最大价值，由于不选即是体积等于0，故最高价值为0
         填表顺序：
         从上到下，从左到右
         */

        //1 创建dp表
        int[][] dp = new int[n+1][V+1];
        int[][] dpp = new int[n+1][V+1];
        //2 初始化 - 只有dpp的第一行1下标之后的元素需要初始化为-1
        for(int k = 1; k <= V; k++)
            dpp[0][k] = -1;
        //3 填表
        int[] ret = new int[2];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                int tmp = j - item[i][1];
                //(1)
                dp[i][j] = dp[i-1][j];
                if(tmp>=0) {
                    dp[i][j] = Math.max(item[i][2]+dp[i-1][tmp],dp[i][j]);
                }
                ret[0] = Math.max(ret[0],dp[i][j]);
                //(2)
                dpp[i][j] = dpp[i-1][j];
                if(tmp>=0 && dpp[i-1][tmp]!=-1) {
                    dpp[i][j] = Math.max(dpp[i][j],item[i][2]+dpp[i-1][tmp]);
                }
                if(j==V) ret[1] = Math.max(dpp[i][j],ret[1]);
            }
        }
        //4 返回值
        System.out.println(ret[0]);
        System.out.println(ret[1]);
    }

}
